package Topological;
import java.util.*;

public class AlienDictionary {
    Map<Character, Integer> in = new HashMap<>(); // 记录各字符的入度情况 A - 2, 表示 A 字符入度有2
    Map<Character, Set<Character>> edges = new HashMap<>(); // 邻接表存图结构
    boolean check = false;

    public String alienOrder(String[] words) {
        // 1.初始化入度
        for (String s : words) {
            for (int i = 0; i < s.length(); i++) {
                // 先把所有出现过的字符入度设置为 0
                char ch = s.charAt(i);
                in.put(ch, 0);
            }
        }

        // 2.建图
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                compareDic(words[i], words[j]);
                if(check == true) {
                    return "";
                }
            }
        }

        // 3.拓扑排序
        Queue<Character> queue = new LinkedList<>();
        // (1) 把入度为 0 的点放到队列中
        for (char c : in.keySet()) {
            if (in.get(c) == 0) {
                // 把该顶点放到队列中
                queue.offer(c);
            }
        }

        // (2) BFS
        StringBuilder ret = new StringBuilder();
        while (!queue.isEmpty()) {
            // 取出入度为 0 的点
            char a = queue.poll();
            ret.append(a);

            // 删除 a 的出度
            // 拿出 a 的出度字符
            for (char b : edges.getOrDefault(a, new HashSet<>())) {
                // 删除 b 的入度
                in.put(b, in.get(b) - 1);
                if (in.get(b) == 0) {
                    // 如果 b 的入度删除后变为 0, 加入到队列中
                    queue.offer(b);
                }
            }
        }

        // 如果入度哈希表中存在不为 0 的元素, 说明该图中有环
        for (char c : in.keySet()) {
            if (in.get(c) != 0) {
                return "";
            }
        }
        return ret.toString();
    }

    public void compareDic(String w1, String w2) {
        int n = Math.min(w1.length(), w2.length());
        int index = 0;
        while (index < n) {
            // a -> b
            char a = w1.charAt(index), b = w2.charAt(index);
            if (a != b) {
                // 更新图结构
                if (!edges.containsKey(a)) {
                    edges.put(a, new HashSet<>());
                }
                // 防止出现重复key-value键值对
                if (!edges.get(a).contains(b)) {
                    // 如果 a 的出度字符没有 b, 才能添加 b, 并且 b 的入度 + 1
                    edges.get(a).add(b);

                    // 更新入度情况
                    in.put(b, in.get(b) + 1);
                }
                break;
            }
            index++;
        }

        if(index == w2.length() && index < w1.length()) {
            check = true;
        }
    }
}
